#include <iostream>
#include <vector>
#include <string>
#include <cmath>
#include <cstdlib>
#include <cstdint>
#include <ctime>
#include <stack>

using namespace std;

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};

class Solution {
public:
    ListNode* head;
    ListNode* head2;
public:
    bool hasCycle(ListNode *head) {
        ListNode* ref1 = head;
        ListNode* ref2 = head;
        while (ref1 && ref2){
            ref1 = ref1->next;
            ref2 = ref2->next;
            if (ref2){
                ref2 = ref2->next;
            }else{
                return false;
            }
            if (ref1 == ref2){
                return true;
            }
        }
        return false;
    }
};

ListNode* createList(int num, uint32_t max)
{
    ListNode* head;
    ListNode* node;
    if (0 == num) return NULL;
    srand(clock());
    head = new ListNode(rand()%max);
    node = head;
    for (int i = 0; i < num-1; i++){
        node->next = new ListNode(rand()%max);
        node = node->next;
    }
    return head;
}

ListNode* createPalindromeList(int num, uint32_t max)
{
    ListNode* head;
    ListNode* node;
    stack<int> mystack;
    if (0 == num) return NULL;
    srand(clock());
    head = new ListNode(rand()%max);
    node = head;
    mystack.push(head->val);

    for (int i = 1; i < num; i++){
        int value = rand()%max;
        if (i < num / 2){
            mystack.push(value);
        }else if (num % 2 == 0 || i > num / 2){
            value = mystack.top();
            mystack.pop();
        }
        node->next = new ListNode(value);
        node = node->next;
    }
    return head;
}

void printList(ListNode* node)
{
    int cnt = 0;
    cout << "node print start:" << endl;
    while(node){
        cout << ++cnt << ":" << node->val << endl;
        node = node->next;
    }
    cout << "node print end" << endl;
}

int main(void)
{
    Solution su;
    su.head = createList(21, 100);
    printList(su.head);
    bool result = su.hasCycle(su.head);
    printf("result is %d\r\n", result);
    return 0;
}
